public class Solution {
    //插入数据时，调整堆。
    public static void up(int i, int[] array){
        //如果该节点的父亲存在
        while(i>=0 && (i-1)/2>=0){
            //如果比父亲大，交换位置
            if(array[i]>array[(i-1)/2]){
                exchange(i,(i-1)/2,array);
                i = (i-1)/2;
            }else {
                break;
            }
        }
    }
    public  static void exchange(int i, int j, int[] array){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    public static void down(int i,int[] array, int N){
        //使得节点i最大。调整儿子位置
        //最大的儿子
        int max;
        while(i<=N/2-1){
            //只有一个左儿子
            if(2*i+2>=N)
                max = 2*i+1;
            else max = (array[2*i+2]>array[2*i+1])?2*i+2:2*i+1;//有两个儿子，就挑个大的
            //如果小于儿子，交换
            if(array[i]<array[max]){
                exchange(i,max,array);
                i = max;
            }else{//自己最大跳出来
                break;
            }
        }
    }
    public static void MaxHeap(int[] array){
        //从最后的非叶子节点开始调整
        for(int i=(array.length-1)/2;i>=0;i--){
            down(i,array,array.length);
        }
    }

    public static void HeapSort(int[] array)
    {
        MaxHeap(array);
        //从小到大的顺序
        int N = array.length;

        for(int i=0; i<array.length-1; i++){
            exchange(0,--N,array);
            down(0,array,N);
        }
    }

    public static void main(String args[]){
        int[] array={1,5,2,6,4,7,9,3};
        MaxHeap(array);
        HeapSort(array);
        System.out.println();
    }

}

